A purpose of error detection techniques, such as techniques based on cyclic redundancy codes (CRCs), is to enable the receiver of a message transmitted through a noisy channel to determine whether the message has been corrupted. To do this, the transmitter generates a value (called a Frame Check Sequence or FCS) that is a function of the message, and typically appends the FCS to the message. The receiver can then use the same function used to generate the FCS of the received message to see if the message was correctly received.
With CRC algorithms, message bits are treated as binary coefficients of an n-bit polynomial. The message polynomial is typically multiplied by xm, where m is the CRC polynomial (i.e., “generator polynomial”) order. The result of the multiplication is divided by the CRC polynomial. Most implementations use a method that simultaneously executes the multiplication by xm and the division by the CRC polynomial, rather than doing these operations in sequential order. The result of these operations is the FCS, which is typically complemented and appended to the message. In some cases, the FCS is not complemented, and occasionally the FCS is put in another location, such as in a header field.
The receiver divides the received message with the appended FCS by the CRC polynomial. Assuming that the FCS was complemented before being appended to the message, and that no errors occurred during transmission, the result of the division at the receiver will be a fixed value equal to the result of dividing the order 2 m polynomial (with coefficients of 1 for the upper m terms, and coefficients of 0 for the lower m terms) by the CRC polynomial. This fixed value is sometimes called the “magic number,” and depends on the polynomial. If the result of the division is not equal to the magic number, this indicates that an error occurred.
The method by which most CRC algorithms are specified involves describing the CRC polynomial, the initial and final states of the CRC computation, whether or not the input (data stream) is complemented prior to processing, and whether or not the result (the CRC) is complemented prior to being appended to the data stream that is being protected by the CRC. In addition, the algorithm may indicate the swapping of bytes to accommodate Little and Big Endian processors. Sample test patterns are usually provided to verify that the CRC algorithm implementation is correct.
A problem commonly faced by designers of software or hardware CRC algorithms is that, when the CRC algorithm produces incorrect results, there is little information to determine at which step of the process the algorithm failed. The sample test patterns typically do not help much, as the patterns only tell the implementer of the algorithm what to expect when the entire process is done, and the patterns provide no information about intermediate states of the CRC computation.